package tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description: 700. 二叉搜索树中的搜索
 * User: Li_yizYa
 * Date: 2025/6/5
 * Time: 21:54
 */
public class Solution27 {
    /**
     * 非递归（队列）
     * @param root
     * @param val
     * @return
     */
    public TreeNode searchBST2(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.val == val) {
                return node;
            } else if (node.val > val && node.left != null) {
                queue.offer(node.left);
            } else if (node.right != null) {
                queue.offer(node.right);
            }
        }
        return null;
    }

    /**
     * 非递归（栈）
     * @param root
     * @param val
     * @return
     */
    public TreeNode searchBST1(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node.val == val) {
                return node;
            } else if (node.val > val && node.left != null) {
                stack.push(node.left);
            } else if (node.right != null) {
                stack.push(node.right);
            }
        }
        return null;
    }
    /**
     * 递归
     * @param root
     * @param val
     * @return
     */
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        }
        if (root.val > val) {
            return searchBST(root.left, val);
        } else if (root.val < val) {
            return searchBST(root.right, val);
        }
        return null;
    }
}
